package com.algorithm;

import java.util.Random;

/**
 * 求数组中第K个最大项的问题方法2,基本思路
 * 把前k个元素读入数组并以递减的顺序对其排序.(此时arr[k-1]为第k大值)接着将剩下的元素逐个读入,当新元素被读到时,如果它小于数组中的第k个元素,忽略之,否则
 * 将其放到数组中的正确位置,同时将数组中的最后一个元素挤出数组.
 * Created by houjinxin on 16/5/3.
 */
public class KMaxOptionType2 {

    private static int[] intArray;

    static {
        intArray = new int[20];
        Random random = new Random();
        for (int i = 0; i < intArray.length; i++) {
            intArray[i] = random.nextInt();
        }
        printArray(intArray);
    }

    public static void main(String[] args) {
        int k = 10;
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) { //前k个元素读入数组
            arr[i] = intArray[i];
        }
        maopao(arr);
        printArray(arr);
        for (int j = k; j < intArray.length; j++) {
            if (intArray[j] < arr[k - 1]) { //若元素小于第k个元素,忽略之
                System.out.println("arr[k - 1]-intArray[j]=" + (arr[k - 1] - intArray[j]));
                continue;
            } else {
                //若元素大于第k个元素,放到arr的正确位置上
                //1.遍历数组找到第一个比intArray[j]小的位置,取得索引值l
                //2.拷贝索引值之前的元素到新数组,将intArray[j]赋值给arr[l],拷贝原数组的索引为l的元素直到原数组的倒数第二项
                //3.原数组的引用指向新数组
                for (int l = 0; l < k; l++) {
//                    System.out.println(arr[l] < intArray[j]);
                    if (arr[l] < intArray[j]) {
                        int[] destArr = new int[k];
                        //拷贝arr[l]前的元素
                        System.arraycopy(arr, 0, destArr, 0, l);
                        destArr[l] = intArray[j];
                        //拷贝arr[l]后的元素一直到倒数第二个
                        System.arraycopy(arr, l, destArr, l + 1, k - l - 1);
                        arr = destArr;
                        break; //已经放到正确的位置无需继续遍历
                    }
                }
            }
        }
        printArray(arr);
        System.out.println("第" + k + "大的是:" + arr[k - 1]);

    }

    /**
     * 逆序(由大到小)的冒泡排序
     */
    public static void maopao(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }

    /**
     * 调换两个元素的位置
     *
     * @param i 元素索引
     * @param j 元素索引
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void printArray(int[] array) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (Integer num : array) {
            sb.append(num + ",");
        }
        System.out.println(sb.substring(0, sb.length() - 1) + "]");
    }
}
